/*

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题报告：

a + b = 0

so==> (a | b) < 0 . (b | a) > 0
---------------------------------
array = {-4, -1, -1, 0, 1, 2} 

because:array is sorted 

so: just Find all lower than 0

thus: {-4, -1, -1}
---------------------------------
*/
#include <iostream>
#include <map>
#include <string>
#include <deque>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>
std::vector<std::vector<int>> threeSum(std::vector<int>& nums)
{
    std::set<std::vector<int>> rst;
    std::sort(nums.begin(), nums.end());
    for (int k = 0; k != nums.size(); ++k) {
        if (nums[k] > 0) {break;}
        int target = 0 - nums[k];
        int i = k + 1, j = nums.size() - 1;
        while (i < j) {
            if (nums[i] + nums[j] == target) {
                rst.insert({nums[i], nums[j], nums[k]});
                /////////////////////////////////////////////////////////////////////
                while (i < j && nums[i] == nums[i+1]) {++i;}    //学到了，对于已经排序后
                while (i < j && nums[j] == nums[j-1]) {--j;}    //的数组如何去重
                ////////////////////////////////////////////////////////////////////
                ++i;
                --j;
            } else if (nums[i] + nums[j] < target) {
                ++i;
            } else {
                --j;
            }
        }
    }
    return std::vector<std::vector<int>>(rst.begin(), rst.end());
}
int main(int argc, const char * argv[])
{
    std::vector<int> nums = {-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0};
    threeSum(nums);
    return 0;
}
